/*
 * @lc app=leetcode.cn id=127 lang=golang
 *
 * [127] 单词接龙
 */

// 4. 广度优先 再优化 每次从栈的前面取 从后面插 也是一层一层下来的
//
// 当层数变得很深的时候，搜索代价成指数级增长，可以考虑双向广度优先，能有效减少搜索次数
// 比如二叉树索搜到第八层才找到那么 需要遍历的次数2^0 + ... + 2^7，
// 但是双向的话只需要查询两个4层的遍历就可以，低于2^7
// 层数越深效果越好
// @lc code=start
func ladderLength(beginWord string, endWord string, wordList []string) int {
	if !contain(wordList, endWord) {
		return 0
	}

	graph := map[string][]string{}
	addGraph := func(word string) {
		temp := []string{}
		bytes := []byte(word)
		for i, v := range bytes {
			bytes[i] = '*'
			temp = append(temp, string(bytes))
			if _, ok := graph[string(bytes)]; !ok {
				graph[string(bytes)] = []string{word}
			} else {
				graph[string(bytes)] = append(graph[string(bytes)], word)
			}
			bytes[i] = v
		}
		graph[word] = temp
	}

	addGraph(beginWord)
	for _, word := range wordList {
		addGraph(word)
	}

	distance := make(map[string]int)
	for word, _ := range graph {
		distance[word] = math.MaxInt64
	}
	distance[beginWord] = 0

	queue := []string{beginWord}
	for len(queue) > 0 {
		word := queue[0]
		queue = queue[1:]

		if word == endWord {
			return distance[word]/2 + 1
		}
		for _, v := range graph[word] {
			if distance[v] == math.MaxInt64 {
				distance[v] = distance[word] + 1
				queue = append(queue, v)
			}
		}

	}

	return 0
}

// @lc code=end

// 3. 广度优先 优化 -- 顶到34/50超时了
// @lc code=start
func ladderLength(beginWord string, endWord string, wordList []string) int {
	if !contain(wordList, endWord) {
		return 0
	}

	graph := map[string][]string{}
	addGraph := func(word string) {
		temp := []string{}
		bytes := []byte(word)
		for i, v := range bytes {
			bytes[i] = '*'
			temp = append(temp, string(bytes))
			if _, ok := graph[string(bytes)]; !ok {
				graph[string(bytes)] = []string{word}
			} else {
				graph[string(bytes)] = append(graph[string(bytes)], word)
			}
			bytes[i] = v
		}
		graph[word] = temp
	}

	addGraph(beginWord)
	for _, word := range wordList {
		addGraph(word)
	}

	history := []string{beginWord}
	level := []string{beginWord}
	ans := 0
	for {
		nextLevel := []string{}
		for i := 0; i < len(level); i++ {
			if level[i] == endWord {
				return ans/2 + 1
			}

			for _, v := range graph[level[i]] {
				if !contain(history, v) {
					history = append(history, v)
					nextLevel = append(nextLevel, v)
				}
			}
		}

		if len(nextLevel) == 0 {
			return 0
		}

		ans++
		level = nextLevel
	}

	return 0
}

func contain(wordList []string, value string) bool {
	for i := 0; i < len(wordList); i++ {
		if wordList[i] == value {
			return true
		}
	}
	return false
}

// @lc code=end

// 2. 广度优先--到33/50超时了
// @lc code=start
func ladderLength(beginWord string, endWord string, wordList []string) int {
	if !contain(wordList, endWord) {
		return 0
	}

	ans := 0
	allWord := "qwertyuiopasdfghjklzxcvbnm"
	var recursion func(words, history []string, count int)
	recursion = func(words, history []string, count int) {
		for _, word := range words {
			if word == endWord {
				ans = count
				return
			}
		}

		nextLevel := []string{}
		for _, word := range words {
			for i := 0; i < len(word); i++ {
				for j := 0; j < len(allWord); j++ {
					if word[i] == allWord[j] {
						continue
					}

					bytes := []byte(word)
					bytes[i] = allWord[j]
					temp := string(bytes)

					if contain(wordList, temp) && !contain(history, temp) {
						nextLevel = append(nextLevel, temp)
					}
				}
			}
		}

		if len(nextLevel) > 0 {
			recursion(nextLevel, append(history, nextLevel...), count+1)
		}
	}
	recursion([]string{beginWord}, []string{beginWord}, 1)

	return ans
}

func contain(wordList []string, value string) bool {
	for i := 0; i < len(wordList); i++ {
		if wordList[i] == value {
			return true
		}
	}
	return false
}

// @lc code=end

// 1. 这个是深度优先--到23/50超时了
// @lc code=start
func ladderLength(beginWord string, endWord string, wordList []string) int {
	ans := math.MaxInt64
	allWord := "qwertyuiopasdfghjklzxcvbnm"
	var recursion func(word string, history []string, count int)
	recursion = func(word string, history []string, count int) {
		if word == endWord {
			ans = min(ans, count)
			return
		}

		for i := 0; i < len(word); i++ {
			for j := 0; j < len(allWord); j++ {
				if word[i] == allWord[j] {
					continue
				}

				bytes := []byte(word)
				bytes[i] = allWord[j]
				temp := string(bytes)

				if contain(wordList, temp) && !contain(history, temp) {
					recursion(temp, append(history, temp), count+1)
				}
			}
		}

	}
	recursion(beginWord, []string{}, 1)

	if ans == math.MaxInt64 {
		return 0
	}
	return ans
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func contain(wordList []string, value string) bool {
	for i := 0; i < len(wordList); i++ {
		if wordList[i] == value {
			return true
		}
	}
	return false
}

// @lc code=end

